package com.wt.springsamples.test;

import java.util.HashMap;
import java.util.Map;

/**
 * 字符串出现次数的top k问题
 * 二叉堆：是一颗完全二叉树，任意结点的键值总是小于（或者大于）它的父节点
 */
public class CountTopK {
    public static void main(String[] args) {
        String[] arrays = new String[]{"apache","node","coyote","status","util","org","java","apache","status","entry","apache"};
        CountTopK countTopK = new CountTopK();
        countTopK.printTopKAndRank(arrays,2);
    }

    public void printTopKAndRank(String[] arr, int topK) {
        if (arr == null || topK < 1) return;
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        //生成哈希表（字符串词频）
        for (int i = 0; i != arr.length; i++) {
            String cur = arr[i];
            if (!map.containsKey(cur)) {
                map.put(cur, 1);
            } else {
                map.put(cur, map.get(cur)+1);
            }
        }

        Node[] heap = new Node[topK];
        int index = 0;
        //遍历哈希表，决定每条信息是否进堆
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            String str = entry.getKey();
            int times = entry.getValue();
            Node node = new Node(str, times);
            if (index != topK) {
                heap[index] = node;
                heapInsert(heap, index++);
            } else {
                if (heap[0].times < node.times) {
                    heap[0] = node;
                    heapIfy(heap, 0, topK);
                }
            }
        }
        //把小根堆的所有元素按词频从大到小排序
        for(int i = index - 1; i != 0; i--) {
            swap(heap, 0, i);
            heapIfy(heap, 0, i);
        }
        //严格按照排名打印k条记录
        for(int i = 0; i != heap.length; i++) {
            if(heap[i] == null) {
                break;
            } else {
                System.out.println("No." + (i + 1) +": "+heap[i].str+", times "+heap[i].times);
            }
        }
    }

    public void heapInsert(Node[] heap, int index) {
        while(index != 0) {
            int parent = (index - 1) / 2;
            if (heap[index].times <heap[parent].times) {
                swap(heap, parent, index);
                index = parent;
            } else {
                break;
            }
        }
    }

    /**
     * 小根堆
     * @param heap 数组
     * @param index 索引
     * @param heapSize 堆大小
     */
    public void heapIfy(Node[] heap, int index, int heapSize) {
        int left = index * 2 + 1;
        int right = index *2 + 2;
        int smallest = index;
        while (left < heapSize) {
            if (heap[left].times  < heap[index].times) {
                smallest = left;
            }
            if (right < heapSize && heap[right].times < heap[smallest].times) {
                smallest = right;
            }
            if (smallest != index) {
                swap(heap, smallest, index);
            } else {
                break;
            }
            index = smallest;
            left = index * 2 + 1;
            right  = index * 2 + 2;
        }
    }

    public void swap(Node[] heap, int index1, int index2) {
        Node tmp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = tmp;
    }
}
class Node {
    public String str;
    public int times;
    public Node(String s, int t) {
        str = s;
        times = t;
    }
}
